package com.lc.weekly.lc426.q3;

import java.util.*;

public class Main {

}


class Solution {
	private List<Integer>[] buildTree(int[][] edges) {
		int n = edges.length + 1;
		List<Integer>[] g = new ArrayList[n];
		
		Arrays.setAll(g, i -> new ArrayList<>());
		
		for (int[] e: edges) {
			int x = e[0];
			int y = e[1];
			g[x].add(y);
			g[y].add(x);
		}
		return g;
	}
	
	
    public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {
    	
    	int n = edges1.length + 1;
    	int m = edges2.length + 1;
    	
    	
    	List<Integer>[] g1 = buildTree(edges1);
    	List<Integer>[] g2 = buildTree(edges2);
    	
    	
    	Map<Integer, Integer> mp1 = new HashMap<>();
    	for (int j = 0; j < n; j ++) {
    		int node = j;
    		Queue<Integer> queue = new LinkedList<>();
    		queue.add(node);
    		int path = 0;
    		int cnt = 0;
    		Set<Integer> set = new HashSet<>();
    		while(!queue.isEmpty() && path <= k) {
    			
    			int size = queue.size();
    			cnt += size;
    			System.out.println(size);
    			for (int i = 0; i < size; i ++) {
    				int tnode = queue.peek();
    				set.add(tnode);
    				queue.poll();

    				List<Integer> list = g1[tnode];
    				
    				for (int e: list) {
    					if (!set.contains(e)) {
    						queue.add(e);
    					}
    				}
    			}
    			path ++;
    		}
    		mp1.put(node, cnt);
    	}
    	
    	
    	int maxv = 0;
    	for (int j = 0; j < m; j ++) {
    		int node = j;
    		Queue<Integer> queue = new LinkedList<>();
    		queue.add(node);
    		int path = 0;
    		int cnt = 0;
    		Set<Integer> set = new HashSet<>();

    		while(!queue.isEmpty() && path < k) {
    			
    			int size = queue.size();
    			cnt += size;
    			for (int i = 0; i < size; i ++) {
    				int tnode = queue.peek();
    				set.add(tnode);
    				queue.poll();

    				List<Integer> list = g2[tnode];
    				for (int e: list) {
    					if (!set.contains(e)) {
    						queue.add(e);
    					}
    				}
    			}
    			path ++;
    		}
    		maxv = Math.max(maxv, cnt);
    	}
    	
    	int[] res = new int[n];
    	
    	for (int i = 0; i < n; i ++) {
    		res[i] = mp1.get(i) + maxv;
    	}
    	return res;
    	
    }
}